Computer storage devices (such as magnetic and optical disk drives) typically employ error correction codes to correct errors in the recorded data due to noise corrupting the carrier signal during the recording/reproduction process. In error correction coding, the binary data to be recorded are processed mathematically to generate redundancy symbols that are appended to the data to form codewords which are written to the disk storage medium. Upon readback, the recorded codewords are estimated (detected) from the read signal, and the redundancy symbols are used to decode the estimated codewords back into the originally recorded user data. The redundancy symbols provide, in effect, a buffer which shields the codeword from noise as it passes through the recording channel. When enough noise "penetrates" this buffer, it mutates a written codeword into a different received codeword, thereby resulting in an error when decoded into the user data.
The more redundancy symbols employed in an error correction code, the larger the buffer around the codeword and the more noise that can be tolerated before a decoding error occurs. However, there is an upper bound on the performance of any given recording channel known as the "channel capacity" which refers to the maximum user data transmission rate (or recording density) achievable for a given channel while maintaining an arbitrarily low bit error rate. Ultimately, the channel capacity is a function of the channel bandwidth and the signal to noise (SNR) ratio. For bandlimitted channels, such as in the typical computer storage system, error correction codes are a means for improving performance by increasing the effective SNR.
There are many approaches to encoding/decoding the user data in order to maximize the reliability and efficiency of a recording channel; ultimately the goal is to design a system that approaches the channel capacity while minimizing the implementation complexity and cost. Examples of error correction codes typically employed in computer storage devices range from simple Hamming codes to more complex, but more powerful and efficient codes, such as the Reed-Solomon block code or convolutional codes. Most of the popular error correction codes, such as the Reed-Solomon code, exploit mathematical properties over finite fields to implement the error correction capabilities.
Finite fields, or Galois fields (GF), are fields comprising a finite number of elements. The order of a finite field is the number of elements it contains. A finite field of order p.sup.n, denoted GF(p.sup.n), exists for every prime p and every positive integer n. The prime p of a finite field GF(p.sup.n) is called the characteristic of the field. The field GF(p) is referred to as the ground field and GF(p.sup.n) is called an extension field of GF(p). The field GF(p.sup.n) can also be denoted GF(q) where q=p.sup.n.
Most error correction codes of a practical interest are defined over fields of characteristic 2 (i.e., GF(2.sup.n)). The finite field GF(2) has only two elements (0,1). Larger fields can be defined by polynomials with coefficients from GF(2). If a polynomial p(x) of degree n with coefficients from GF(2) is primitive and .alpha. is a root of p(x), then the powers of .alpha. up through 2.sup.n -2 will all be unique. Appropriately selected operations of addition and multiplication together with the field elements EQU 0, 1, .alpha..sup.1, .alpha..sup.2, .alpha..sup.3, . . . , .alpha..sup.2n-2
define a field of 2.sup.n elements GF(2.sup.n).
Consider, for example, that a finite field is defined by the polynomial EQU p(x)=x.sup.3 +x+1.
Since .alpha. is a root of p(x), p(.alpha.)=0. Therefore, EQU .alpha..sup.3 +.alpha.+1=0 and .alpha..sup.3 =.alpha.+1.
The field elements for this field are generated by successively computing EQU .alpha..sup.j+1 =.alpha..sup.j .multidot..alpha..
The elements are
0=0
.alpha..sup.0 =1
.alpha..sup.1 =.alpha..sup.1
.alpha..sup.2 =.alpha..sup.2
.alpha..sup.3 =.alpha.+1
.alpha..sup.4 =.alpha..multidot..alpha..sup.3 =.alpha..multidot.(.alpha.+1)=.alpha..sup.2 +.alpha..sup.1
.alpha..sup.5 =.alpha..multidot..alpha..sup.4 =.alpha..multidot.(.alpha..sup.2 +.alpha.)=.alpha..sup.3 +.alpha..sup.2 =.alpha..sup.2 +.alpha..sup.1 +1
.alpha..sup.6 =.alpha..multidot..alpha..sup.5 =.alpha..multidot.(.alpha..sup.2 +.alpha.+1)=.alpha..sup.3 +.alpha..sup.2 +.alpha.=.alpha..sup.2 +1
The elements of this field can be represented in binary fashion by using one bit to represent each of the three powers of .alpha. whose sum comprises an element as shown in Table 1:
TABLE 1 ______________________________________ ##STR1## ______________________________________
It is well known that decoding an error correction code entails processing the estimated codeword data mathematically using certain finite field arithmetic operations. With Reed-Solomon codes, for example, each symbol of the data stream is typically selected from a finite field GF(2.sup.n) where n is the number of binary data bits in a symbol. Each symbol of the k-symbol input block represents the coefficients of a data polynomial D(x). The redundancy symbols (which are also represented as a polynomial W(x)) are then computed as the modulo division of the input data polynomial D(x) by a generator polynomial G(x): EQU W(x)=(x.sup.m .multidot.D(x))MOD G(x)
where m is the degree of the generator polynomial which equals the number of redundancy symbols. The redundancy polynomial W(x) is then added to the data polynomial D(x) to generate a codeword polynomial C(x): EQU C(x)=(x.sup.m .multidot.D(x))+W(x)
The encoder circuitry for performing the above operations can be implemented simply as a linear feedback shift register (LFSR).
After encoding, the codeword C(x) is transmitted through the noisy communication channel, wherein the received codeword C'(x) equals the transmitted codeword C(x) plus an error polynomial E(x). The received codeword C'(x) is corrected according to the following steps: (1) compute error syndromes S.sub.i ; (2) compute the coefficients of an error locator polynomial using the error syndromes S.sub.i ; (3) compute the roots of the error locator polynomial, the logs of the roots are the error locations L.sub.i ; (4) compute the error values using the error syndromes S.sub.i and the roots of the error locator polynomial.
The error syndromes S.sub.i are computed as the modulo division of the received codeword polynomial C'(x) by the factors of the generator polynomial G(x): EQU S.sub.i =C'(x)MOD(x+.alpha..sup.i)
when ##EQU1## where .alpha. is a primitive element of the finite field GF(2.sup.n). Techniques for performing the other steps of the decoding process, computing the error locator polynomial, computing the roots of the error locator polynomial, and computing the error values, are well known by those skilled in the art (see the above referenced U.S. patent REED-SOLOMON CODE SYSTEM EMPLOYING K-BIT SERIAL TECHNIQUES FOR ENCODING AND BURST ERROR TRAPPING).
There are different methods in the prior art for generating the error locator polynomial from which the error locations and values can be determined. Typically, these methods require the finite field division operation and may also require the finite field logarithm operation depending on the implementation. In the single error case, for example, the error locator polynomial is EQU x+.sigma.
where .sigma.=S.sub.1 /S.sub.0 (S.sub.0 and S.sub.1 are the error syndromes described above). Thus, the coefficient .sigma. is computed by dividing the S.sub.1 syndrome by the S.sub.0 syndrome. The logarithm of .sigma., LOG(.sigma.) , is the location of the error within the received codeword polynomial C'(x) and the error value is simply the error syndrome S.sub.0.
The logarithm of an element is defined as EQU LOG.sub..alpha. (x)=LOG.sub..alpha. (.alpha..sup.j)=j.
For example, the logarithm of the fifth element in Table 1 above corresponding to .alpha..sup.3 =011 is EQU LOG.sub..alpha. (011)=LOG.sub..alpha. (.alpha..sup.3)=3.
The logarithm operation is typically implemented as a lookup table on the order of the field size. That is, the field element x in LOG.sub..alpha. (x) is used to address a lookup table of size 2.sup.n with n bits per entry (i.e., n bits per element). This technique, however, is not cost effective when the size of the field increases in order to increase the power of the error correction code. For example, to compute the logarithm of a finite field GF(2.sup.8) requires a lookup table (e.g., a ROM) on the order of 256 by 8 bits.
The division operation is another finite field operation typically requiring a lookup table. Division in a finite field is carried out by taking the inverse of the denominator element and then multiplying. For example EQU .alpha..sup.i /.alpha..sup.j =.alpha..sup.i .multidot.(1/.alpha..sup.j).
The inverse operation (1/.alpha..sup.j) is computed as ##EQU2## Similar to computing the logarithm of an element, computing the inverse of an element is typically implemented using a lookup table on the order of the field size, which is inefficient as the field size grows. The above U.S. patent entitled "FINITE FIELD INVERSION" discloses a cost reduced method for computing the inverse of a field element without a lookup table, but the circuitry disclosed in that patent only implements the inversion operation and does not share circuitry for computing a logarithm of a field element.
There is, therefore, a need for a finite field processor that can compute the logarithm of a finite field element in a more cost effective manner. Another object of the present invention is to share circuitry for computing both the logarithm and inversion of a finite field element, thereby obviating the cost of lookup tables typically employed in the prior art.